class DisjointSetUnion           // 并查集（按秩合并）
{
private:
    vector<int> f, rank;         // 图的联通关系、和记录各节点的秩
    int numOfJoint;
public:
    DisjointSetUnion(int n)
    {
        numOfJoint = n;
        rank.resize(n, 1);       // 各节点的秩均为1
        f.resize(n);
        for (size_t i = 0; i < n; i++)
        {
            f[i] = i;
        }
    }

    int find(int x)
    {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    void unionSet(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx == fy)
        {
            return;
        }
        if (rank[fx] < rank[fy])
        {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        f[fy] = fx;              // 秩小的指向秩大的，减少搜索叶节点的用时
    }
};

class Solution
{
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs)
    {
        DisjointSetUnion dsu(s.length());
        for (size_t i = 0; i < pairs.size(); i++)
        {
            dsu.unionSet(pairs[i][0], pairs[i][1]);
        }

        unordered_map<int, vector<int>> mp;
        for (size_t i = 0; i < s.length(); i++)
        {
            mp[dsu.find(i)].emplace_back(s[i]);  // 建立哈希映射的过程中同步构建查并集
        }
        unordered_map<int, vector<int>>::iterator iter = mp.begin();
        for (; iter != mp.end(); iter++)         // 按最小字典序，对最小联通集进行排序
        {
            sort(iter->second.begin(), iter->second.end(), greater<int>());
        }
        for (size_t i = 0; i < s.length(); i++)
        {
            int x = dsu.find(i);
            s[i] = mp[x].back();
            mp[x].pop_back();
        }

        return s;

    }
};